package com.xyhuo.leetcode.november;

import java.util.ArrayList;
import java.util.List;

/**
 * 最长回文串
 * https://leetcode.cn/problems/longest-palindromic-substring
 *
 * @time 2023/11/24
 */
public class LongestPalindrome {

//        public static void main(String[] args) {
//        LongestPalindrome longestPalindrome = new LongestPalindrome();
//        String s = longestPalindrome.longestPalindrome("a");
//    }

    public String longestPalindrome(String s) {
        char[] charArray = s.toCharArray();
        int length = charArray.length;
        List<List<Integer>> dp = new ArrayList<>();
        List<Integer> first = new ArrayList<>();
        first.add(1);
        dp.add(first);
        int result = 1;
        int index = 0;
        for (int i = 1; i < length; i++) {
            List<Integer> list = new ArrayList<>();
            char curChar = charArray[i];
            if (charArray[i - 1] == curChar) {
                list.add(2);
                if (2 > result) {
                    result = 2;
                    index = i;
                }
            }
            if (i - 2 >= 0 && charArray[i - 2] == curChar) {
                list.add(3);
                if (3 > result) {
                    result = 3;
                    index = i;
                }
            }
            List<Integer> lastList = dp.get(i - 1);
            if (null != lastList && !lastList.isEmpty()) {
                for (Integer item : lastList) {
                    if (i - 1 - item >= 0 && charArray[i - 1 - item] == curChar) {
                        list.add(item + 2);
                        if (item + 2 > result) {
                            result = item + 2;
                            index = i;
                        }
                    }
                }
            }
            dp.add(list);
        }
        return s.substring(index - result + 1, index + 1);
    }
}
